1. Field of the Invention
This invention relates to error correction and detection and, more particularly, to systems that employ error codes to detect and correct bit errors.
2. Description of the Relevant Art
Error codes are commonly used in electronic systems to detect and correct data errors, such as transmission errors or storage errors. For example, error codes may be used to detect and correct errors of data transmitted via a telephone line, a radio transmitter, or a compact disc laser. Error codes may additionally be used to detect and correct errors of data stored in the memory of computer systems. One common use of error codes is to detect and correct errors of data transmitted on a data bus of a computer system. For example, error correction bits, or check bits, may be generated for data prior to transferring the data on a data bus. When the data are received, the check bits may be used to detect and correct errors within the data. Errors may be introduced either due to faulty components or noise within the computer system. Faulty components may include faulty memory devices, faulty bus interface units, or faulty data paths between devices within a system, such as faulty pins, faulty data traces, or faulty wires.
Hamming codes are a commonly used type of error code. The check bits in a Hamming code are parity bits for portions of the data bits. Each check bit provides the parity for a unique subset of the data bits. If an error occurs, i.e. one or more bits change state, one or more of the check bits will change state (assuming the error is within the class of errors covered by the code). Information regarding the particular check bits that change state may also be used to determine which data bit changes state, and to correct the error. For example, if one data bit changes state, this data bit will modify one or more check bits. Because each data bit contributes to a unique group of check bits, the check bits that are modified will identify the data bit that changed state. The error may be corrected by inverting the bit identified to be erroneous.
One common use of Hamming codes is to correct single bit errors within a group of data. Generally speaking, the number of check bits must be large enough such that 2.sup.k-1 is greater than or equal to n, where k is the number of check bits and n is the number of data bits plus the number of check bits. Accordingly, seven check bits are required to implement a single error correcting Hamming code for 64 data bits. A single error correcting Hamming code is capable of detecting and correcting a single error.
In a single error correcting Hamming code, a set of syndrome bits is generated upon receipt of data. The syndrome bits are used to detect a single bit error. The syndrome bits further identify the position of the error, and thus can be used to correct the single bit error by inverting a value in the identified position. However, single bit error correcting Hamming codes fail to detect two bits errors which may occur during the transfer of data. Further, multiple bit errors may erroneously appear as a single bit error and may cause an incorrect identification of a position of the erroneous bit. Therefore, a bit that is not erroneous may be inverted. In the latter situation, the error correction procedure creates more errors and may erroneously indicate that the data is correct.
The error detection capability of the code may be increased by adding an additional check bit. The use of an additional check bit allows the Hamming code to detect two single bit errors and to detect and correct single bit errors. The addition of a bit to increase the error detection capabilities of a Hamming code is referred to as an extended Hamming code. The extended check bit is regenerated when the syndrome bits are generated. The regenerated extended check bit is compared to the original extended parity bit. If one or more syndrome bits are asserted and the regenerated extended parity bit is different than the original extended check bit, a single bit error has occurred and is corrected. Alternatively, if one or more syndrome bits are asserted and the regenerated extended parity bit is the same as the original extended check bit, two bit errors are detected and no correction is performed. In the latter case, an uncorrectable error may be reported to a bus interface unit or other component within the computer system. It is noted that more than two bit errors in a logical group is not within the class of errors addressed by the error correction code. Accordingly, three or more errors may go undetected or the error correction code may interpret the errors as a single bit error and invert a data bit that was not erroneous.
It is a common design goal in computer systems to reduce the number of check bits used to detect and correct errors. The check bits increase the amount of data handled by the system, which may increase the circuitry and data paths required for transferring the data. Further, the increased number of bits increases the probability of an error. Although the check bits may make an error detectable and/or correctable, increasing the number of bits within the system increases the probability of an error occurring. For at least these reasons, it is desirable to decrease the number of check bits for a given level of error detection and/or correction.